

$m = shift;#global variable for the type of model

$n = shift;#global variable for the number of sentances that should be printed

print $m."-gram with ".$n. " examples.\n";

initialize();#initialises data structures

while(<>){#while there are more lines from file to read in

    my @line = format_line();#formats the text to the correct form used

    parse_line_ngram(@line);#parses the line according to the current ngram


}

for($i = 0; $i < $n; $i++){

    generate_sentence();

}


################################################################################
#formats the incoming text
#returns array of tokens in correct format

sub format_line{

    chomp;#removes newline characters

    s/(\.|\?|\!|\"|\;|\'|\,)/ $1 /g;#puts spaces between punctutation

    s/(.*)/lc($1)/e;#puts it all into lowercase

    my @line = split;#splits up all of the tokens

    return @line;
   
}


################################################################################
#initializes the data structures

sub initialize{

    %word_combinations;

    %tokens = ();

    @ngram = ();#create the ngram structure

    $count = 0;

    while($count < $m){
  
    push(@ngram, "<s>");#put n number of starting elements in it

    $count += 1;

    }

}

################################################################################
#parses the line according to this runs n value

sub parse_line_ngram{

    foreach $word(@_){
	
	#$add = 1;

	#foreach $entry(@tokens){#checks to see if word is already on tokens list
	    
	#    if($word eq $entry){
		
	#	$add = 0;
		
	#    }
	#}

	#if($add){

	#    push(@tokens, $word);#adds word to tokens list

	#}

	#print "@tokens";

	if($tokens{$word} != 1){

	    $tokens{$word} = 1;

	}

	shift(@ngram);#takes first token off

	push(@ngram, $word);#puts new token on end

	#print "@ngram"."\n";

	my $ngram_string = "";#string form of @ngram

	foreach $token(@ngram){#append each token of @ngram onto $ngram_string
	    
	    $ngram_string = $ngram_string.$token;

	}

	if($word_combinations{$ngram_string}){#if the hash entry exists already

	    #print "made it here\n";

	    $word_combinations{$ngram_string} += 1;

	}else{#hash entry does not exist already

	    $word_combinations{$ngram_string} = 1;

	}


	if($word =~ /[!.?]/){#reached sentance boundary
	    sentence_boundary();#set ngram back to beginning of new sentence
	}

    }

    #while (($key, $value) = each(%word_combinations)){
	#print $key."~> ".$value."\n";
    #}

}

################################################################################
#sets ngram back to the beginning of a sentance

sub sentence_boundary{

    @ngram = ();

    $count = 0;

    while($count < $m){
  
    push(@ngram, "<s>");

    $count += 1;

    }

}


################################################################################
#generates a random sentence based off the probabilities of the input files

sub  generate_sentence{

    print "This is sentence: ".$i."\n";

    sentence_boundary();#resets the @ngram to beginning of sentence

    pop(@ngram);#take one <s> off of @ngram

    $boundary = 1;#this means we have not met a boundary class

    while(($boundary)){

	%cond_probs = get_cond_prob(@ngram);

	#print %cond_probs."\n";

	$w = choose_word(\%cond_probs);

	push(@ngram, $w);

	$boundary = boundary_check(@ngram);

	shift(@ngram);
    
	print $w." ";

	#print "\n";

    }
    
    print "\n";

}


#################################################################################
#generates conditional probablities based on the @ngram given
#param1 @ngram

sub get_cond_prob{

    my @ngram = @_;

    my $ngram_string = "";#string form of @ngram
 
    my %cond_probs = ();
   
    foreach $token(@ngram){#append each token of @ngram onto $ngram_string
	    
	$ngram_string = $ngram_string.$token;

    }

    while (($token, $val) = each(%tokens)){

	#print $word_combinations{$ngram_string.$token};
	$value = $word_combinations{$ngram_string.$token};
	
	$total += $value;

	if($value > 0){

	    $cond_probs{$token} = $value;

	}

    }

     while (($token, $val) = each(%tokens)){

	#print $word_combinations{$ngram_string.$token};
	if($cond_probs{$token}){
	    $cond_probs{$token} = ($word_combinations{$ngram_string.$token}/$total);
	}

    }

    $total = 0;

    return %cond_probs;

}


#################################################################################
#takes a list of conditional probabilities and randomly chooses one based on its
#probability
#param1: %cond_probs

sub choose_word{

    my (%cond_probs) = %{$_[0]};

    $prob_total = 0;

    while (($key, $value) = each(%cond_probs)){
	#print "prob total is ".$prob_total."\n";
	$cond_probs{$key} = $value + $prob_total;
	$prob_total += $value;

    }

    #print %cond_probs;

    $rand_num = rand(1);

    while (($key, $value) = each(%cond_probs)){

	if($cond_probs{$key} >= $rand_num){
	
	    return $key;

	}

    }

}

################################################################################
#checks for sentence boundary

sub boundary_check{

    my @ngram = @_;

    if($ngram[$m-1] =~ /[!.?]/){

	return 0;#we have reached a sentence boundary

    }else{

	return 1;#we have not reached a sentencce boundary

    }


}
